package huawei.dstack;

/**
 * https://leetcode-cn.com/problems/sum-of-subarray-minimums/
 */
public class J907 {
    public static void main(String [] args){
        System.out.println(sumSubarrayMins(new int[]{3,1,2,4}));//17
        System.out.println(sumSubarrayMins(new int[]{11,81,94,43,3}));//444
    }
    private static final int MOD = (int) (Math.pow(10,9)+7);
    public static int sumSubarrayMins(int[] arr) {
        int sum = 0;
        int[] stack = new int[arr.length];
        int stackLen =0;
        int tmp =0;
        for (int i = 0; i < arr.length; i++) {
            while (stackLen>0&&arr[stack[stackLen-1]]>arr[i]){
                stackLen--;
                int last =stackLen>0?stack[stackLen-1]:-1;
                tmp=tmp-(arr[stack[stackLen]]-arr[i])*(stack[stackLen]-last);
            }

            tmp=(tmp+arr[i]);
            System.out.println(tmp);
            sum=(sum+tmp);
            stack[stackLen++]=i;
        }
        return sum%MOD;
    }

    /**
     * 最优
     * @param A
     * @return
     */
    public int sumSubarrayMins2(int[] A) {
        long res=0;
        long sum=0;
        int stack[]=new int[A.length+1];
        int length=0;
        stack[length++]=-1;
        for(int i=0;i<A.length;i++){
            while(length>1 && A[stack[length-1]]>=A[i]){
                sum-=A[stack[length-1]]*(stack[length-1]-stack[length-2]);
                length--;
            }
            sum+=A[i]*(i-stack[length-1]);
            res+=sum;
            stack[length++]=i;
        }
        return (int)(res % 1000000007);

    }
}
